Search Results

Documents authored by Bullinger, Martin

Document
DOI: 10.4230/LIPIcs.ESA.2023.27
Online Coalition Formation Under Random Arrival or Coalition Dissolution

Authors: Martin Bullinger and René Romen

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
Coalition formation considers the question of how to partition a set of n agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with additively separable aggregation of preferences and study the online variant of coalition formation, where the agents arrive in sequence and whenever an agent arrives, they have to be assigned to a coalition immediately. The goal is to maximize social welfare. In a purely deterministic model, the greedy algorithm, where an agent is assigned to the coalition with the largest gain, is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities. We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is Θ(1/(n²)), whereas an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of Θ(1/n). Second, we relax the irrevocability of decisions by allowing to dissolve coalitions into singleton coalitions, presenting a matching-based algorithm that once again achieves a competitive ratio of Θ(1/n). Hence, compared to the base model, we present two ways to achieve a competitive ratio that precisely gets rid of utility dependencies. Our results also give novel insights in weighted online matching.
Cite as

Martin Bullinger and René Romen. Online Coalition Formation Under Random Arrival or Coalition Dissolution. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bullinger_et_al:LIPIcs.ESA.2023.27,
  author =	{Bullinger, Martin and Romen, Ren\'{e}},
  title =	{{Online Coalition Formation Under Random Arrival or Coalition Dissolution}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.27},
  URN =		{urn:nbn:de:0030-drops-186809},
  doi =		{10.4230/LIPIcs.ESA.2023.27},
  annote =	{Keywords: Online Algorithms, Coalition Formation, Online Matching}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.26
Boundaries to Single-Agent Stability in Additively Separable Hedonic Games

Authors: Martin Bullinger

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Coalition formation considers the question of how to partition a set of agents into coalitions with respect to their preferences. Additively separable hedonic games (ASHGs) are a dominant model where cardinal single-agent values are aggregated into preferences by taking sums. Output partitions are typically measured by means of stability, and we follow this approach by considering stability based on single-agent movements (to join other coalitions), where a coalition is defined as stable if there exists no beneficial single-agent deviation. Permissible deviations should always lead to an improvement for the deviator, but they may also be constrained by demanding the consent of agents involved in the deviations, i.e., by agents in the abandoned or welcoming coalition. Most of the existing research focuses on the unanimous consent of one or both of these coalitions, but more recent research relaxes this to majority-based consent. Our contribution is twofold. First, we settle the computational complexity of the existence of contractually Nash stable partitions, where deviations are constrained by the unanimous consent of the abandoned coalition. This resolves the complexity of the last classical stability notion for ASHGs. Second, we identify clear boundaries to the tractability of stable partitions under majority-based stability concepts by proving elaborate hardness results for restricted classes of ASHGs. Slight further restrictions lead to positive results.
Cite as

Martin Bullinger. Boundaries to Single-Agent Stability in Additively Separable Hedonic Games. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bullinger:LIPIcs.MFCS.2022.26,
  author =	{Bullinger, Martin},
  title =	{{Boundaries to Single-Agent Stability in Additively Separable Hedonic Games}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-168249},
  doi =		{10.4230/LIPIcs.MFCS.2022.26},
  annote =	{Keywords: Coalition Formation, Hedonic Games, Stability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact